//
//  Train. 插入排序.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/18.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/*
 前面是有序的，后面时无序的
 从后面选择一个在插入前面的有序表里。这样就需要挪动
 **/
class SolutionInsertSortTrain {
    func insertSort(_ nums: inout [Int]) {
        guard nums.count > 1 else {
            return
        }
        for i in 1..<nums.count {
            let tmp = nums[i]
            var index = i - 1
            for j in (0..<i).reversed() {
                if nums[j] > tmp {
                    nums[j + 1] = nums[j]
                    index = j
                }
            }
            nums[index] = tmp
        }
    }
    static func test() {
        var nums = [156,141,35,94,88,61,111]
        let solution = SolutionInsertSortTrain()
        solution.insertSort(&nums)
        print(nums)
    }
}
